#include <iostream>
#include <cmath>
#include <cstring>

#define SIZE 1000000002
             
using namespace std;

char list[SIZE];

void criba(int limit){
   memset(list, 1, sizeof(list));

   int d_limit = (int) (sqrt(limit));

   for(int i=2; i<=d_limit; i++){
      if(list[i]){
         for(int j=2; j*i<=limit; j++){
            list[j*i] = 0;
         }
      }
   }
}

void criba(int L,int U){
   int d = U-L+1;
   int d_limit = (int) (sqrt(U));
	
   memset(list, 1, sizeof (char [d]));

   for(int i = (L % 2 == 1); i < d; i += 2){
      list[i] = 0;
   }

   for(int i = 3; i <= d_limit; i += 2){
      if (i > L && !list[i-L]) continue;

      int j = L/i*i;
    
      if (j < L) j += i;
      if (j == i) j += i;
      j-=L; 
      for (; j < d; j += i) 
         list[j]=0;
   }
  
   if (L <= 1) list[1-L] = 0;
   if (L <= 2) list[2-L] = 1;
  
/*  for (int i = 0; i < d;i++) 
	  if (list[i]) cout << (L+i) << " ";
	  
  cout << endl;*/
}

bool is_prime(int n){
   if(n < 2 ) return false;
   
   for (int i = 2; i < (int)sqrt(n) + 1; i++){
      if (n % i == 0) 
         return false;
   }
   return true;
}

int main() {
   int limit = 100000;
    
   for(int i = 10000000; i  < 100000000; i++)
      if(is_prime(i)) 
         cout << i << endl;
   
   criba(100000000);
	
   criba(100000000-10, 100000000);

   return 0;
}

